Many service providers need to authenticate a device before extending the service to that device. A good authentication system will also protect the privacy and identity of the device from malicious attacks. When the number of devices requesting the service is large, it is a challenge to scale up the authentication process yet providing reasonable response time. This is the challenge that is faced in many Radio-Frequency Identification (RFID) applications.
In RFID systems, RF tags emit their unique serial numbers to RF readers when they are being interrogated. Without privacy protection, however, any reader can identify a tag ID via the emitted serial number. Indeed, within the scanning range, a malicious reader can easily perform bogus authentication with detected tags to retrieve sensitive information. Currently, as most tags indicate the unique information of the items, a customer carrying those tags is subject to silent track from unauthorized readers. Sensitive personal information might be exposed. Clearly, a secure RFID system must meet two requirements. On the one hand, a valid reader must be able to identify the valid tags; on the other hand, misbehaving readers should not be able to retrieve private information from those tags.
In order to protect user privacy, Privacy-Preserving Authentication (PPA) is introduced into the interactive procedure between RFID readers and tags. To achieve PPA, an RFID tag performs a cryptography enabled challenging-response procedure with a reader. For example, we can let each tag share a distinct key with the reader. During authentication, the reader first probes a tag via a query message with a nonce. Instead of using the plaintext to directly answer the query, the tag encrypts the nonce and reply the cipher to the reader. The back-end database of the reader searches all keys that it holds, and finds a proper key to recover the authentication message (if it does find one), and thereby identifies the tag. (For simplicity, we will use the term “reader” to denote the reader device as well the back-end database in what follows) If the tag is invalid, it cannot provide a proper cipher related to a key owned by the reader. In this procedure, the tag does not expose its identity to any third party. Meanwhile, the key used for encrypting messages is only known by valid readers. A malicious reader cannot identify a user via probing the valid tag.
Being simple and secured, such a PPA based design suffers poor scalability. Upon receiving a cipher of nonce, the reader needs a prompt lookup to locate a key in the database. Clearly, the search complexity is O(N), where N is the number of all the possible tags, even only a small portion of them are in the reader's range. In today's large-scale RFID systems, N is often as large as hundreds of millions, and thousands of tags may respond to a reader simultaneously, demanding a fast key-search method as well as a carefully designed key-storage structure. Hence, balance-tree based schemes are proposed to accelerate the authentication procedure, in which the lookup complexity is O(log N).
The existing balance-tree based approaches are efficient, nevertheless, not secured due to the key-sharing feature of balance-trees. As the key storage infrastructure of balance-tree based approaches is static, each tag, more or less, shares some common portions of keys with other tags (we use normal tags to denote those tags which are not tampered with). Consequently, compromising one tag might reveal information of other tags. L. Lu et al. evaluate the damage caused by compromising attacks to balance tree-based approaches: In a RFID system containing 220 tags, and employing binary tree as the key tree, an adversary, by compromising only 20 tags, has a probability of nearly 100% to be able to track normal tags.
To mitigate the impact of compromising attacks, L. Lu et al. propose a dynamic key-updating scheme, Strong and lightweight RFID Private Authentication protocol (SPA), for balance tree-base approaches. The key-updating of SPA reduces the number of keys shared among compromised and normal tags, and alleviate the damage caused by compromising attacks. SPA, however, does not completely eliminate the impact of compromising attacks. For instance, using SPA in a RFID system with 220 tags, the probability of tracking normal tags is near to 60% after an adversary compromises 20 tags.
Another drawback for balance-tree based PPAs is the large space needed to store keys in each tag. Balance-tree based approaches require each tag to hold O(logδY) keys, and the reader to store δ·N keys, where δ is a branch factor of the key tree. Obviously, due to the limited memory capacity of current RF tags, existing PPAs are difficult to be applied in current RFID systems.